package com.caochenlei.greedyAlgorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class BroadcastCoverage {
    public static void main(String[] args) {
        //创建广播电台集合
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

        //将各个电台存起来
        HashSet<String> broadcast1 = new HashSet<>();
        broadcast1.add("北京");
        broadcast1.add("上海");
        broadcast1.add("天津");
        broadcasts.put("K1", broadcast1);
        HashSet<String> broadcast2 = new HashSet<>();
        broadcast2.add("广州");
        broadcast2.add("北京");
        broadcast2.add("深圳");
        broadcasts.put("K2", broadcast2);
        HashSet<String> broadcast3 = new HashSet<>();
        broadcast3.add("成都");
        broadcast3.add("上海");
        broadcast3.add("杭州");
        broadcasts.put("K3", broadcast3);
        HashSet<String> broadcast4 = new HashSet<>();
        broadcast4.add("上海");
        broadcast4.add("天津");
        broadcasts.put("K4", broadcast4);
        HashSet<String> broadcast5 = new HashSet<>();
        broadcast5.add("杭州");
        broadcast5.add("大连");
        broadcasts.put("K5", broadcast5);

        //存放被覆盖的地区
        HashSet<String> allAreas = new HashSet<String>();
        allAreas.addAll(broadcast1);//会自动去除重复元素
        allAreas.addAll(broadcast2);//会自动去除重复元素
        allAreas.addAll(broadcast3);//会自动去除重复元素
        allAreas.addAll(broadcast4);//会自动去除重复元素
        allAreas.addAll(broadcast5);//会自动去除重复元素

        //输出最后选择结果
        System.out.println(selectBroadcasts(broadcasts, allAreas));
    }

    //核心代码
    public static ArrayList<String> selectBroadcasts(HashMap<String, HashSet<String>> broadcasts, HashSet<String> allAreas) {
        ArrayList<String> selects = new ArrayList<>();      //存放选择电台集合
        HashSet<String> tempSet = new HashSet<>();          //存放电台覆盖地区和当前还没有覆盖地区的交集
        while (allAreas.size() != 0) {                      //只要当前的地区集合没有被全部覆盖就接着循环
            String maxKey = null;                           //存放能够覆盖最大未覆盖的地区对应电台的key
            for (String key : broadcasts.keySet()) {
                tempSet.clear();                            //清空掉tempSet
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);                      //添加到tempSet
                tempSet.retainAll(allAreas);                //获取tempSet和allAreas的交集然后放到tempSet
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {                           //如果这次找到最大key
                selects.add(maxKey);                        //添加到选择电台集合
                allAreas.removeAll(broadcasts.get(maxKey)); //删除已覆盖电台地区
            }
        }
        return selects;
    }
}
